# 199.二叉树的右视图
# 给定一个二叉树的根节点root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
#
# 示例1:
# 输入: [1, 2, 3, null, 5, null, 4]
# 输出: [1, 3, 4]
#
# 示例2:
# 输入: [1, null, 3]
# 输出: [1, 3]
#
# 示例3:
# 输入: []
# 输出: []

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def rightSideView(self, root):
        # 其实就是层序遍历取最后一个值
        que = []
        res = []
        if not root:
            return res
        que.append(root)
        while que:
            size = len(que)
            tmp = []
            for i in range(size):
                node = que.pop(0)
                if i == size-1:
                    res.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            # res.append(tmp[-1])
        return res

    # 参考算法，值得借鉴
    def rightSideView1(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        # deque来自collections模块，不在力扣平台时，需要手动写入
        # 'from collections import deque' 导入
        # deque相比list的好处是，list的pop(0)是O(n)复杂度，deque的popleft()是O(1)复杂度

        quene = deque([root])
        out_list = []

        while quene:
            # 每次都取最后一个node就可以了
            node = quene[-1]
            out_list.append(node.val)

            # 执行这个遍历的目的是获取下一层所有的node
            for _ in range(len(quene)):
                node = quene.popleft()
                if node.left:
                    quene.append(node.left)
                if node.right:
                    quene.append(node.right)

        return out_list


if __name__ == '__main__':
    a32 = TreeNode(7)
    a31 = TreeNode(15)
    a21 = TreeNode(9)
    a22 = TreeNode(20,a31,a32)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    res = tmp.rightSideView(a11)
    print(res)
